package cn.jietuo.first.class02;

import java.util.Stack;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2020/6/18
 * @description: 实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能
 * 1）pop、push、getMin操作的时间复杂度都是 O(1)。
 * 2）设计的栈类型可以使用现成的栈结构。
 */
public class Code05_GetMinStack {

    public static class MyStack {

        /** 数据栈 */
        private Stack<Integer> dataStack;
        /** 最小值栈 */
        private Stack<Integer>  minStack;

        public MyStack(){
            dataStack = new Stack<Integer>();
            minStack = new Stack<Integer>();
        }

        /**
         * 压栈
         * @param value
         */
        public void push(Integer value){
            dataStack.push(value);
            if (minStack.isEmpty()){
                minStack.push(value);
            }else{
                // 比较minStack栈顶元素与被加入的元素的大小，push小的元素
                minStack.push(Math.min(value.intValue(),minStack.peek().intValue()));
            }
        }

        /**
         * 弹栈
         * @return
         */
        public Integer pop(){
            if (dataStack.isEmpty()){
                throw new RuntimeException("your stack is empty");
            }
            minStack.pop();
            return dataStack.pop();
        }

        /**
         * 获取最小值
         * @return
         */
        public Integer getMin(){
            if (minStack.isEmpty()){
                throw new RuntimeException("your stack is empty");
            }
            return minStack.peek();
        }

    }
}
